{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Losers of the Circular Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: circularGameLosers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出转圈游戏输家"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 个朋友在玩游戏。这些朋友坐成一个圈，按 <strong>顺时针方向</strong> 从 <code>1</code> 到 <code>n</code> 编号。准确的说，从第 <code>i</code> 个朋友的位置开始顺时针移动 <code>1</code> 步会到达第 <code>(i + 1)</code> 个朋友的位置（<code>1 &lt;= i &lt; n</code>），而从第 <code>n</code> 个朋友的位置开始顺时针移动 <code>1</code> 步会回到第 <code>1</code> 个朋友的位置。</p>\n",
    "\n",
    "<p>游戏规则如下：</p>\n",
    "\n",
    "<p>第 <code>1</code> 个朋友接球。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>接着，第 <code>1</code> 个朋友将球传给距离他顺时针方向 <code>k</code> 步的朋友。</li>\n",
    "\t<li>然后，接球的朋友应该把球传给距离他顺时针方向 <code>2 * k</code> 步的朋友。</li>\n",
    "\t<li>接着，接球的朋友应该把球传给距离他顺时针方向 <code>3 * k</code> 步的朋友，以此类推。</li>\n",
    "</ul>\n",
    "\n",
    "<p>换句话说，在第 <code>i</code> 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 <code>i * k</code> 步的朋友。</p>\n",
    "\n",
    "<p>当某个朋友第 2 次接到球时，游戏结束。</p>\n",
    "\n",
    "<p>在整场游戏中没有接到过球的朋友是 <strong>输家</strong> 。</p>\n",
    "\n",
    "<p>给你参与游戏的朋友数量 <code>n</code> 和一个整数 <code>k</code> ，请按升序排列返回包含所有输家编号的数组 <code>answer</code> 作为答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, k = 2\n",
    "<strong>输出：</strong>[4,5]\n",
    "<strong>解释：</strong>以下为游戏进行情况：\n",
    "1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。\n",
    "2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。\n",
    "3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。\n",
    "4）第 3 个朋友接到两次球，游戏结束。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 4\n",
    "<strong>输出：</strong>[2,3,4]\n",
    "<strong>解释：</strong>以下为游戏进行情况：\n",
    "1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。\n",
    "2）第 1 个朋友接到两次球，游戏结束。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-losers-of-the-circular-game](https://leetcode.cn/problems/find-the-losers-of-the-circular-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-losers-of-the-circular-game](https://leetcode.cn/problems/find-the-losers-of-the-circular-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n2', '4\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularGameLosers(self, n: int, k: int) -> List[int]:\n",
    "        a = [0] * n\n",
    "        x = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if a[x] == 1:\n",
    "                break\n",
    "            a[x] = 1\n",
    "            x = (x + i * k) % n\n",
    "        return [i + 1 for i in range(n) if a[i] == 0]\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularGameLosers(self, n: int, k: int) -> List[int]:\n",
    "        visit = [False] * n\n",
    "        i = k\n",
    "        j = 0\n",
    "        while not visit[j]:\n",
    "            visit[j] = True\n",
    "            j = (j + i) % n\n",
    "            i += k\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if not visit[i]:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularGameLosers(self, n: int, k: int) -> List[int]:\n",
    "        # while true，从0~ n 范围内轮询，每次index加一，步长为index*k % 5，将下一个位置添加到新列表中\n",
    "        # 判断，如果位置编码在列表中已经存在，则跳出while循环\n",
    "        # 判断，在位置列表中轮询，将每个编号从原始列表中删除\n",
    "        # 输出，删除后的原始列表，每个元素加一\n",
    "        index = 0\n",
    "        next_id = 0\n",
    "        win_list = [0]\n",
    "        while True:\n",
    "            index += 1\n",
    "            next_id += index * k\n",
    "            next_id = next_id % n\n",
    "            # 判断，如果位置编码在列表中已经存在，则跳出while循环\n",
    "            if next_id in win_list:\n",
    "                break\n",
    "            win_list.append(next_id)\n",
    "        # 判断，在位置列表中轮询，将每个编号从原始列表中删除\n",
    "        tmp_answer = []\n",
    "        answer = []\n",
    "        for i in range(n):\n",
    "            if i not in win_list:\n",
    "                tmp_answer.append(i)\n",
    "        # 输出，删除后的原始列表，每个元素加一\n",
    "        for each_id in tmp_answer:\n",
    "            answer.append(each_id + 1)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def circularGameLosers(self, n: int, k: int) -> List[int]:\n",
    "        ball_received_players = set()\n",
    "        crt = 0\n",
    "        move = k\n",
    "        while 1:\n",
    "            if crt in ball_received_players:\n",
    "                break\n",
    "            ball_received_players.add(crt)\n",
    "            crt = (crt + move) % n\n",
    "            move += k\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i not in ball_received_players:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
